package com.c2b.algorithm.leetcode.jzoffer.tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * <a href = "https://www.nowcoder.com/practice/435fb86331474282a3499955f0a41e8b?tpId=13&tqId=23294&ru=%2Fpractice%2F94a4d381a68b47b7a8bed86f2975db46&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&sourceUrl=">二叉树的深度</a>
 * <p>
 * 输入一棵二叉树，求该树的深度。
 * 从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度，根节点的深度视为 1 。
 * </p>
 * <pre>
 *     假如输入的用例为{1,2,3,4,5,#,6,#,#,7}，那么如下图:
 *          1
 *        /   \
 *       2     3
 *      / \     \
 *     4   5     6
 *        /
 *       7
 *      返回值：4
 * </pre>
 *
 * @author c2b
 * @since 2023/3/9 11:11
 */
public class JzOffer0055TreeMaxDepth_I {
    /**
     * 递归
     * <p>
     * step 1：对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.<br>
     * step 2：递归分别计算左子树与右子树的深度。<br>
     * step 3：当前深度为两个子树深度较大值再加1。<br>
     * </p>
     */
    public int TreeDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(TreeDepth(root.left), TreeDepth(root.right)) + 1;
    }

    public int TreeDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        // 队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 先把根节点入队
        queue.offer(root);
        // 当前层数
        int level = 0;
        while (!queue.isEmpty()) {
            // 当前层节点的个数
            TreeNode node;
            // 遍历本层节点，将下层节点全部入队
            for (int i = 0; i < queue.size(); i++) {
                // 弹出队首节点，并将其左子节点和右子节点压入队列。
                node = queue.poll();
                if (node.right != null) {
                    queue.offer(node.right);
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
            }
            // 本层节点遍历完成，层数+1，进入下一层
            level++;
        }
        return level;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.right = new TreeNode(6);
        root.left.right.left = new TreeNode(7);
        JzOffer0055TreeMaxDepth_I jzOffer0055TreeDepth = new JzOffer0055TreeMaxDepth_I();
        System.out.println(jzOffer0055TreeDepth.TreeDepth2(root));
    }
}
